package com.dexter.year2023.charpter5_queue_map.level1;

/**
 * 用链表实现Queue
 *
 * @author Dexter
 */
public class LinkedQueue {
    /**
     * 这里的front类似dummy
     */
    private Node front;
    private Node rear;
    private int size;

    static class Node {
        public int data;
        public Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 构造方法
     */
    public LinkedQueue() {
        this.front = new Node(0);
        this.rear = new Node(0);
    }

    /**
     * 入队，从链表尾部插入
     */
    public void push(int value) {
        Node newNode = new Node(value);
        // 找到原来的尾结点
        Node temp = front;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        rear = newNode;
        size++;
    }

    /**
     * 出队，从链表头部删除
     */
    public int poll() {
        if (front.next == null) {
            System.out.println("队列已空");
        }
        Node firstNode = front.next;
        // 虚拟头连接现有第一名的next，即删除第一名
        front.next = firstNode.next;
        size--;
        return firstNode.data;
    }

    /**
     * 遍历打印
     */
    public void traverse() {
        Node temp = front.next;
        while (temp != null) {
            System.out.print(temp.data + "\t");
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        // 测试用例
        LinkedQueue linkedQueue = new LinkedQueue();
        linkedQueue.push(1);
        linkedQueue.push(2);
        linkedQueue.push(3);
        System.out.println("第一个出队的元素为：" + linkedQueue.poll());
        System.out.println("当前队列中剩余元素：");
        linkedQueue.traverse();
    }

}
